Основные классы функций для асимптотики

Рассматриваем только бесконечно большие (при $n \to \infty$) функции. Бесконечно малые получаются как обратные к бесконечно большим. **Полиномиальные функции**: функции, для которых существуют $\alpha, \beta > 0$ такие, что $f(n) = O(n^\alpha)$ и $f(n) = \Omega(n^\beta)$. Пример: $f(n) = n$. **Экспоненциальные функции**: функции вида $f(n) = 2^{p(n)}$ для некоторой полиномиальной функции $p(n)$. Пример: $f(n) = 2^n$. Часто экспоненциальные функции понимаются в более узком смысле, как $2^{\Omega(n)}$, что получается, если в определении полиномиальной функции потребовать $\beta \ge 1$. **Почти экспоненциальные функции**: функции вида $2^{\sqrt[3]{n}}$ или $2^{\frac{n}{\log n}}$. **Полилогарифмические функции**: функции вида $f(n) = p(\log n)$ для некоторой полиномиальной функции $p(n)$. Пример: $f(n) = \log n$.